`
https://leetcode.cn/problems/validate-binary-tree-nodes/
`

/**
 * @param {number} n
 * @param {number[]} leftChild
 * @param {number[]} rightChild
 * @return {boolean}
 */
var validateBinaryTreeNodes = function (n, leftChild, rightChild) {
  const indegree = new Array(n).fill(0)
  // 计算出每个节点的入度
  for (let i = 0; i < n; i++) {
    if (leftChild[i] !== -1) indegree[leftChild[i]]++
    if (rightChild[i] !== -1) indegree[rightChild[i]]++
  }
  // 应当只有一个根节点，其入度为 0
  // 其他节点的入度都应该只为 1
  let root = -1
  for (let i = 0; i < n; i++) {
    if (indegree[i] === 0) {
      // 找到了两个根节点（入度为 0），不符合
      if (root !== -1) return false
      root = i
    } else if (indegree[i] !== 1) {
      // 其他的节点入度都应该为 1
      return false
    }
  }

  // 如果没找到根节点，也不符合
  if (root === -1) return false

  // 使用 Union-Find 并查集算法，保证树中只有一个联通分量且不成环
  const uf = new UF(n)
  for (let i = 0; i < n; i++) {
    if (leftChild[i] !== -1) {
      // 如果已经连通了，说明有环
      if (uf.connected(leftChild[i], i)) return false
      uf.union(leftChild[i], i)
    }
    if (rightChild[i] !== -1) {
      // 如果已经连通了，说明有环
      if (uf.connected(rightChild[i], i)) return false
      uf.union(rightChild[i], i)
    }
  }

  // 保证只存在一个连通分量，即只有一棵树
  return uf.count() === 1
};

class UF {
  // n 为图中节点的个数
  constructor(n) {
    // 连通分量个数
    this._count = n
    // 存储每个节点的父节点
    this.parent = Array.from({ length: n }, (_, index) => index)
  }

  // 将节点 p 和节点 q 连通
  union(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)

    if (rootP === rootQ) {
      return
    }

    this.parent[rootQ] = rootP
    // 两个连通分量合并成一个连通分量
    this._count--
  }

  // 判断节点 p 和节点 q 是否连通
  connected(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)
    return rootP === rootQ
  }

  // 返回图中的连通分量个数
  count() {
    return this._count
  }

  _find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this._find(this.parent[x])
    }
    return this.parent[x]
  }
}